#include "definitions.h"
#include "Triangulation.h"

using namespace std;
//using namespace boost

Triangulation::Triangulation(void)
{
  m_prepared = false;
}

Triangulation::Triangulation(const Face & face)
{
   SetFace(face);
}

Triangulation::~Triangulation(void)
{
 
}


void Triangulation::SetFace(const Face & face)
{
  edgeForIterator fit;
  edgeRevIterator rit;
  Vertex          v;
  bool            circulation = false;

  //Clear all structures
  m_doublyList.clear();
  m_diagList.clear(); 
  while(!m_vertQueue.empty())
    m_vertQueue.pop();
  while(!m_vertStack.empty())
    m_vertStack.pop();
  //End of clean section

  circulation = ((Face &)face).GetCirculation();
 
  //circulation = true;

  if(circulation)
    fit = (edgeForIterator &)face.begin();
  else
    rit = (edgeRevIterator &)face.rbegin();
    
  if(circulation)
  {
    while(fit != (edgeForIterator &)face.end())
    {
      v = (reinterpret_cast<figureEdge *>(*fit))->_begin;
      m_doublyList.AddElement((reinterpret_cast<figureEdge *>(*fit))->_begin);
      fit ++;
    }
  }else
  {
    while(rit != (edgeRevIterator &)face.rend())
    {
      v = (reinterpret_cast<figureEdge *>(*rit))->_begin;
      m_doublyList.AddElement((reinterpret_cast<figureEdge *>(*rit))->_begin);
      rit ++;
    }
  }
 
  //Prepare to the triangulation
  vertIterator  vIt;

  for(vIt = m_doublyList.begin();
      vIt != m_doublyList.end();
      vIt ++)
  {
    m_vertQueue.push(*vIt);
  }


  //Two first points we push on the stack
  for(int i = 0; i < 2; i++)
  {
    m_vertStack.push(m_vertQueue.top());
    m_vertQueue.pop();
  }
  m_prepared = true;

  /*********************Test
  figureVertice vi;
  while(!m_vertQueue.empty())
  {
    vi = m_vertQueue.top();
    m_vertQueue.pop();
  }
  **************************/
}

void Triangulation::Triangulate()
{
  int loop, size;
  figureVertice vert_stck, vert_que;
  figureVertice vert_prev, vert_next;
  //This is main routine for triangulation 
  assert(m_prepared == true);
  
  size = m_vertQueue.size();
  for(loop = 0; loop < (size - 1); loop++)
  {
    //We take a next point from queue 
    //and we test if point->prev is equal 
    //point from stack :)
    vert_que = m_vertQueue.top();
    m_vertQueue.pop();  //pop the top element from queue

    //Now check if the point is on the same chain 
    vert_stck = m_vertStack.top();
    vert_prev = m_doublyList.GetPrev(vert_que);
    vert_next = m_doublyList.GetNext(vert_que);
    if((vert_prev == vert_stck) || (vert_next == vert_stck))
    {
      IdenticalChain(vert_que);
    }else //the point lies on different chain
    {
      DifferentChain(vert_que);
    }
  }

  m_vertStack.pop();
  vert_que = m_vertQueue.top();
  while(m_vertStack.size() > 1)
  {
    vert_stck = m_vertStack.top();
    AddDiagonal(vert_que,vert_stck);
    m_vertStack.pop();
  }
}



void Triangulation::DifferentChain(const figureVertice & v)
{
  figureVertice vertice;
  //figureEdge    edge;

  m_prevVert = m_vertStack.top();
  vertice    = m_prevVert;
  while(m_vertStack.size() > 1 && !IsAngleCheck(v,vertice))// && !IsIntersection(v, vertice))
  {
    vertice = m_vertStack.top();
    m_vertStack.pop();
    AddDiagonal(v,vertice);
  }
  m_vertStack.pop(); //clean the stack

  m_vertStack.push(m_prevVert);
  m_vertStack.push(v);
}


void Triangulation::IdenticalChain(const figureVertice & v)
{
  figureVertice vertice;
  bool diag_outside = false;

  m_prevVert = m_vertStack.top();
  //vpr = m_vertStack.top();
  m_vertStack.pop();

  while(m_vertStack.size() > 0  && !diag_outside)
  {
    vertice = m_vertStack.top();
    
    if(IsAngleCheck(v,vertice) || IsIntersection(v, vertice)) //180)
    {
      diag_outside = true;
    }else
    {
      AddDiagonal(v,vertice);
      m_vertStack.pop();
      m_prevVert = vertice;
    }
  }
  m_vertStack.push(m_prevVert);
  m_vertStack.push(v);
}

void Triangulation::AddDiagonal(const figureVertice & v1, const figureVertice & v2)
{
  figureEdge    edge;
  if(v1.x > v2.x)
  {
    edge._begin = v2;
    edge._end = v1;
  }else
  {
    edge._begin = v1;
    edge._end = v2;
  }
  m_diagList.insert(edge);
}


bool Triangulation::IsIntersection(const figureEdge & diagonal)
{
  vertIterator it;
  Vector2D v1, v2;
  figureVertice vt, vt2;

  vt = m_doublyList.front();
  for(it = ( ++ m_doublyList.begin());
      it != m_doublyList.end();
      it ++)
  {
    vt2 = (*it);
    if(((*it).x > min(diagonal._begin.x, diagonal._end.x) && 
       (*it).x < max(diagonal._begin.x, diagonal._end.x)) ||
       (vt.x > min(diagonal._begin.x, diagonal._end.x)) && 
       (vt.x < max(diagonal._begin.x, diagonal._end.x)))
    {
      v1.SetVector(vt,(*it));
      v2.SetVector(diagonal._begin, diagonal._end);
      if(v1.CheckCollision(v2, false))
        return true;
    }
    vt = (*it);
  }
  return false;
}

bool Triangulation::IsIntersection(const figureVertice & v1, const figureVertice & v2)
{
  figureEdge diagonal;
  diagonal._begin = v1;
  diagonal._end   = v2;
  return(IsIntersection(diagonal));
}

//TODO: replace vertice.next by m_doublylist
bool Triangulation::IsAngleCheck(const figureVertice & vertice_begin, const figureVertice & vertice_end)
{
  Vector2D v1,v2;
  double angle1, angle2, angle3, angle4;
  bool ret = false;

  //v1.SetVector(v,vertice);
  //v2.SetVector(vertice,m_prevVert);
  //v1.SetVector(v,m_prevVert);
  //v2.SetVector(m_prevVert, vertice);
  //v1.GetFollowVectorAngle(v2, false);
  
  v1.SetVector(vertice_begin, m_doublyList.GetNext(vertice_begin));
  v2.SetVector(vertice_begin, m_doublyList.GetPrev(vertice_begin));
  angle1 = v1.GetVectorAngleCommonBegin(v2);
  v2.SetVector(vertice_begin, vertice_end);
  angle2 = v1.GetVectorAngleCommonBegin(v2);
  //angle1 = v2.GetVectorAngleCommonBegin(v1);
  //v1.SetVector(vertice_begin, vertice_end);
  //angle2 = v2.GetVectorAngleCommonBegin(v1);
  //We need to check if the angle of destination is also ok
  v1.SetVector(vertice_end, m_doublyList.GetNext(vertice_end));
  v2.SetVector(vertice_end, m_doublyList.GetPrev(vertice_end));
  angle3 = v1.GetVectorAngleCommonBegin(v2);
  v2.SetVector(vertice_end, vertice_begin);
  angle4 = v1.GetVectorAngleCommonBegin(v2);
  //angle3 = v2.GetVectorAngleCommonBegin(v1);
  //v1.SetVector(vertice_end, vertice_begin);
  //angle4 = v2.GetVectorAngleCommonBegin(v1);

  //We have to check if the diagonal does not intersect any edgex
  //The intersection has to be different from the start and end point !!!

  if(angle1 <= angle2 || angle3 <= angle4)
  {
    ret = true;
  }
  return ret;
}

void Triangulation::TriangleExtract(const HWND & hwnd, const POINT & shift)
{
  //Configuration cc;
  HDC hdc = GetDC(hwnd);
  diagonalListIterator it;
  figPointsIterator figIt;
  int size;
  //1. If no diagonals exist it means 
  //The face is a triangle 
  //and we can add face to triangle factory
  //m_points

  /*if(cc.GetConfig(DRAW_DIAGONAL))
  {
    for(it = m_diagList.begin();
        it != m_diagList.end();
        it ++)
    {
      MoveToEx(hdc,(*it)._begin.x,(*it)._begin.y,NULL);
      LineTo(hdc,(*it)._end.x,(*it)._end.y);
      Sleep(200);
    }
  }*/
  /*
  m_doublyList.clear();

  size = m_doublyList.size();

  for(figIt = m_doublyList.begin();
      figIt != m_doublyList.end();
      figIt++)
  {
    m_doublyList.AddElement(*(figureVertice *)(*figIt));
  }
  */
  size = m_doublyList.size();

  FindAShortestDiagonalWay();
  

  
 // _ASSERT(m_points.size() == 3); 
/*
  for(figIt = m_points.begin();
      figIt != m_points.end();
      figIt ++)
  {
     *points = *((figureVertice *)(*figIt));
     points++;
  }
*/
}

Vertex Triangulation::GetHighestPoint()
{
  Vertex v;
  vertIterator figIt;

  v = m_doublyList.front();
  for(figIt = m_doublyList.begin();
      figIt != m_doublyList.end();
      figIt ++)
  {
    if(v > (*figIt))
      v = (*figIt);
  }
  return v;
}

const figureEdge & Triangulation::FindDiagonal(Vertex v1, Vertex v2)
{
  diagonalListIterator it;
  for(it = m_diagList.begin();
      it != m_diagList.end();
      it ++)
  {
    if(((*it)._begin == v1 && (*it)._end == v2) ||
      ((*it)._begin == v2 && (*it)._end == v1))
      return *it;
  }
}


void Triangulation::FindAShortestDiagonalWay()
{
  TriangleFactory tFactory;
  Vertex p[3];
  diagonalListIterator it;
  int costway=0;
  Triangle t;
  int size = m_diagList.size();

  size = m_doublyList.size();
  while(m_diagList.size() > 0)
  {
    for(it = m_diagList.begin();
        it != m_diagList.end();
        it ++)
    {
      costway = DiagonalCostWay(*it);
      if(costway == 1 || costway == -1)
      {
        p[0] = (*it)._begin;
        p[1] = ((costway == 1)? m_doublyList.GetNext((*it)._begin): m_doublyList.GetPrev((*it)._begin));
        p[2] = (*it)._end;
        t.SetSides(p);
        tFactory.AddTriangle(t);
        //m_triangles.push_back(t);
        
        m_doublyList.RemoveElement(p[1]);
        size = m_doublyList.size();
        m_diagList.erase(m_diagList.find(*it));
        //size--;
        break;
      }    
    }
  }
  //And last triangle - last 3 points :)
  _ASSERT(m_doublyList.size() == 3);
  size = 0;
  vertIterator vit = m_doublyList.begin();
  for(;vit != m_doublyList.end();
      vit++)
  {
    p[size++] = *vit;
  }
  t.SetSides(p);
  tFactory.AddTriangle(t);
  //return t;
}


int Triangulation::DiagonalCostWay(const figureEdge & diagonal)
{
  Vertex v1, v2;
  int costway = 0;


  v1 = diagonal._begin;
  v2 = diagonal._end;

  while( (v1 = m_doublyList.GetNext(v1)) != v2)
  {
    costway++;
    if(costway > m_doublyList.size())
      break;
  }
  v1 = diagonal._begin;
  if(costway > 1)
  {
    costway = 0;
    while( (v1 = m_doublyList.GetPrev(v1)) != v2)
    {
    costway--;
    if((costway * (-1)) > m_doublyList.size())
      break;
    }
  }
  return costway;
}
